# 用递归实现 迷宫搜索，dfs，但是用为状态保存的原因，实际上是  dfs + bfs

import random

# 迷宫数据
mz = []

# 生成迷宫
def generate_maze(width=3, height=3):
    for i in range(height):
        mz.append([])
        for j in range(width):
            mz[i].append(0)
            p = random.randint(1, 100)
            if p < 20:
                mz[i][j] = 1
    mz[0][0] = 2
    mz[height-1][width-1] = 2

# 显示迷宫和给定的路径
def show_mz(path=[]):
    s = "0123456789\n"
    for i in range(len(mz)):
        for j in range(len(mz[i])):
            if mz[i][j] == 1:
                # print("#", end="")
                s += "#"
            elif mz[i][j] == 2:
                # print("S", end="")
                s += "S"
            elif (i, j) in path:
                # print("*", end="")
                s += "*"
            else:
                # print(" ", end="")
                s += " "

        # print("\n")
        s += f"|{i}\n"  # str(i) + "|\n"
    s += "-"*(len(mz[0])) + "\n"
    return s

# 下一步可以走的位置
def find_next_cell(x, y):
    r = []
    directions = [(0, 1), (1, 0),  (0, -1), (-1, 0)]
    for d in directions:
        nx = x + d[0]
        ny = y + d[1]
        ### 错误：这里应该用mz[nx][ny] != 1，终点要包括。
        if nx >= 0 and nx < len(mz[0]) and ny >= 0 and ny < len(mz) and mz[nx][ny] != 1:
            r.append((nx, ny))
    return r

# 递归实现搜索
def recursion(x, y, visited, level=0):
    if level == 0:
        print("start:", (x, y), "end:", (len(mz)-1, len(mz[0])-1))
    # print()
        
    s = ""
    # 判断是否到达终点
    if (x, y) == (len(mz)-1, len(mz[0])-1):
        s += f"{level} cx:({x},{y}) find.\n"
        s += show_mz(visited)
        return s

    # 标记已访问
    visited.append((x, y))

    # 下一步可以走的位置
    nx = find_next_cell(x, y)
    unvisited = [n for n in nx if n not in visited]

    ss = f"{level} cx:({x},{y}) nx:[" + ",".join(str(n) for n in nx) + "] "
    ss += f"unvisited: ["+",".join(str(n) for n in unvisited)+"] "

    # 无路可走
    if not unvisited:
        s += ss + "end.\n"
        return s
    
    # 继续前进：因为py执行顺序，是dfs的，所有的点都要走，又是bfs的
    for n in unvisited:
        
        ### 错误 没有意思到 py 的传值调用和引用调用的问题
        
        # py的数组是引用传递，如果直接使用，新路径需要时全新的，路径会少很多
        vc = visited
        # 要用浅拷贝，才能发现所有的路径
        vc = visited.copy()

        s += ss + f"next: ({n[0]},{n[1]}) visited: {len(vc)}\n"
        r = recursion(n[0], n[1], vc, level+1)
        s += r
    return s


if __name__ == "__main__":

    # 因为会查找所有路径，所以迷宫不能太大
    mm = 3
    
    generate_maze(mm, mm)

    nx = find_next_cell(9,8)
    print(nx)
    
    s = show_mz()    

    s += recursion(0, 0, [])

    with open("maze.txt", "w") as f:
        f.write(s)